package com.LeeCode;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * 串联所有单词的子串
 */

public class Code030 {
    public static void main(String[] args) {
        String s = "barfoofoobarthefoobarman";
        String[] words = {"bar", "foo", "the"};
        System.out.println(new Code030().findSubstring(s, words));
    }

    public List<Integer> findSubstring(String s, String[] words) {
        List<Integer> result = new ArrayList<>();
        if (words == null || words.length == 0 || s == null || s.length() == 0) {
            return result;
        }

        int wordLen = words[0].length();
        int totalLen = words.length * wordLen;
        int strLen = s.length();

        if (strLen < totalLen) {
            return result;
        }

        // 统计单词频率
        Map<String, Integer> wordCount = new HashMap<>();
        for (String word : words) {
            wordCount.put(word, wordCount.getOrDefault(word, 0) + 1);
        }

        // 遍历所有可能的起始位置（0 到 wordLen - 1）
        for (int i = 0; i < wordLen; i++) {
            int left = i, right = i, count = 0;
            Map<String, Integer> windowCount = new HashMap<>();

            while (right + wordLen <= strLen) {
                String currWord = s.substring(right, right + wordLen);
                right += wordLen;

                if (wordCount.containsKey(currWord)) {
                    windowCount.put(currWord, windowCount.getOrDefault(currWord, 0) + 1);
                    count++;

                    // 收缩窗口
                    while (windowCount.get(currWord) > wordCount.get(currWord)) {
                        String leftWord = s.substring(left, left + wordLen);
                        left += wordLen;
                        windowCount.put(leftWord, windowCount.get(leftWord) - 1);
                        count--;
                    }

                    // 检查是否匹配
                    if (count == words.length) {
                        result.add(left);
                    }
                } else {
                    // 遇到无效单词，重置窗口
                    windowCount.clear();
                    count = 0;
                    left = right;
                }
            }
        }

        return result;
    }
}
